#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/9/26 8:04
# @Author  : Yuyun
# @File    : leetcode_40_组合总和II.py
# @IDE     : PyCharm
"""
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
"""
"""
迭代三部曲：
    1、确认递归函数返回值与参数：candidates,targetSum,结果数组res，子集合path，子集合首元素起始位置startindex
    2、回溯函数终止条件：子集合和 = targetSum则回溯寻找下一组子集
    3、单层搜索过程：
        循环遍历[startindex, len(candidates)]的每个元素i
        剪枝：
            sum(path) > n，则直接回溯寻找子集下一个元素
        path.append(candidates[i])，再递归寻找子集合下一元素，从i + 1寻找；
        若子集合的遍历终止，则回溯path.pop()，遍历下一个元素i + 1。
"""
import traceback
class Solution:
    def combination_total(self, candidates, targetSum, res, startindex, path=[]):
        length = len(path)
        if sum(path) == targetSum:
            res.append(path[:])
            #   回溯，寻找下一组
            return
        for i in range(startindex, len(candidates)):
            #   剪枝，若加入当前元素candidates[i] > targetSum，则不对candidates[i]进行操作
            if sum(path) + candidates[i] > targetSum:
                #   排过序了，后序元素更大，直接不再遍历
                break
            #   对同一层级使用过的元素进行跳过
            if i > startindex and candidates[i] == candidates[i - 1]:
                continue
            path.append(candidates[i])
            self.combination_total(candidates, targetSum, res, i + 1, path)
            #   回溯
            path.pop()

if __name__ == '__main__':
    try:
        # candidates = list(map(int, input().split(',')))
        candidates = eval(input())
        candidates.sort()
        targetSum = int(input())
        res = []
        solution = Solution()
        solution.combination_total(candidates, targetSum, res, 0)
        print(res)
    except Exception as e:
        traceback.print_exc()